package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1447 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public List<String> simplifiedFractions(int n) {
            if (n <= 1) return new ArrayList<>();

            List<String> ans = new ArrayList<>();
            for (int i = 2; i <= n; i++) {
                ans.add("1/" + i);
                for (int j = 2; j < i; j++) {
                    if (maxCommonNum(i, j) == 1) ans.add(j + "/" + i);
                }
            }

            return ans;
        }

        //    辗转相除法

        /**
         * @param left
         * @param right
         * @return 若要用left对right取模，那么要保证left>=right（反之亦然）
         * 1 若left%right==0,则right就是所求的最大公约数
         * 2 若left%right!=0,则将right的值赋给left，将left%riht的值赋给right，即left=right,right=left%right,然后再取模，判断余数是否为0
         * 3 重复这些步骤，直到left%right==0,则right就是所求的最大公约数
         */
        public int maxCommonNum(int left, int right) {
            if (left < right) {
                int temp = left;
                left = right;
                right = temp;
            }
            if (left % right == 0) return right;
            else return maxCommonNum(right, left % right);
        }
    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.maxCommonNum(4, 6));
        System.out.println(solution.simplifiedFractions(2));
        System.out.println(solution.simplifiedFractions(3));
        System.out.println(solution.simplifiedFractions(4));//输出：["1/2","1/3","1/4","2/3","3/4"]
        System.out.println(solution.simplifiedFractions(6));//        预期结果：["1/2","1/3","1/4","1/5","1/6","2/3","2/5","3/4","3/5","4/5","5/6"]
    }

    public static void main(String[] args) throws Exception {
        LC1447 an = new LC1447();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
